//题目:
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// "1" -> 'A'
// "2" -> 'B'
// ...
// "25" -> 'Y'
// "26" -> 'Z'
// 然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
// 例如，"11106" 可以映射为：
// "AAJF" ，将消息分组为 (1, 1, 10, 6)
// "KJF" ，将消息分组为 (11, 10, 6)
// 消息不能分组为  (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。
// 注意，可能存在无法解码的字符串。
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。
// 题目数据保证答案肯定是一个 32 位 的整数。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    // int ret=0;
    int arr[101]={0};//arr[i]记录的是从第i个位置算起的解码方法总数，s[i]!='0'
public:
    //全排列
    // void dfs(const string& s,int pos)
    // {   //1020105657769342
    //     if(pos==s.size())
    //     {
    //         ret++;
    //         return;
    //     }
    //     //由于0会被第二个if跳过，所以s[pos]不可能为0

    //     //a.s[pos+1]不存在,或存在但不为0,才能自己组
    //     if(pos+1==s.size() || s[pos+1]!='0')
    //         dfs(s,pos+1);
    //     //b.且s[pos+1]存在 && 与s[pos]相组合法 && s[pos]不能抢夺s[pos+2]的配对，如:2101 即2不能抢0前面的那个1   
    //     if(pos+1<s.size() && (s[pos]=='1' || (s[pos]=='2' && s[pos+1]>='0' && s[pos+1]<='6')) && (pos+2==s.size() || s[pos+2]!='0'))
    //         dfs(s,pos+2);
    // }

    //记忆化搜索
    int dfs(const string& s,int pos)
    {   //1020105657769342
        if(pos==s.size()) //走到这里，说明这种解码方法是合法的
            return 1;
        if(arr[pos]!=0)return arr[pos];

        int sum=0;//记录s[pos]位置后面的解码方法总数
        //a.要么自己组：s[pos+1]不存在,或存在但不为0,才能自己组
        if(pos+1==s.size() || s[pos+1]!='0')
            sum+=dfs(s,pos+1);
        //b.要么与下一个组：s[pos+1]存在 && 与s[pos]相组合法 && s[pos]不能抢夺s[pos+2]的配对，如:2101 即2不能抢0前面的那个1   
        if(pos+1<s.size() && (s[pos]=='1' || (s[pos]=='2' && s[pos+1]>='0' && s[pos+1]<='6')) && (pos+2==s.size() || s[pos+2]!='0'))
            sum+=dfs(s,pos+2);

        arr[pos]=sum;
        return sum;
    }
    int numDecodings(string s) 
    {
        //应对非法解码的字符串
        for(int i=0;i<s.size();i++)
        {
            //若想使0合法解码，则0前面必须要有一个1或2，否则非法
            if(s[i]=='0' && (i-1==-1 || (s[i-1]!='1' && s[i-1]!='2')))
                return 0;
        }
        //全排列————超时
        // dfs(s,0);
        // return ret;

        //优化————>记忆化搜索
        // return dfs(s,0);

        //动态规划
        int n=s.size();
        //1.创建dp表————dp[i]表示：从第0个位置开始，解码第i个位置的方法总数
        vector<int> dp(n);
        //2.初始化
        dp[0]=1;
        //3.填表————动态转移方程：dp[i]=dp[i-1]+dp[i-2]
        for(int i=1;i<n;i++)
        {
            int sum=0;
            //a.自己组  条件：s[i]不为0
            if(s[i]!='0') sum+=dp[i-1];
            //b.与前一个元素相组  条件：s[i-1]与s[i]相组合法
            if(s[i-1]=='1' || (s[i-1]=='2' && s[i]>='0' && s[i]<='6'))
            {
                if(i-2>=0) sum+=dp[i-2];
                else sum+=1;
            }
            dp[i]=sum;
        }
        return dp[n-1];//返回从0到最后一个位置解码方法总数
    }
};